package leetcode.editor.day;

import java.util.Arrays;

// 1450. 在既定时间做作业的学生人数
// https://leetcode.cn/problems/number-of-students-doing-homework-at-a-given-time/
class NumberOfStudentsDoingHomeworkAtAGivenTime {
    public static void main(String[] args) {
        Solution solution = new NumberOfStudentsDoingHomeworkAtAGivenTime().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 枚举
    /*public int busyStudent(int[] startTime, int[] endTime, int queryTime) {
        int ans = 0;
        for (int i = 0; i < startTime.length; i++) {
            if (startTime[i] <= queryTime && endTime[i] >= queryTime) ans++;
        }
        return ans;
    }*/

        // 差分数组，适合多次查询
    /*public int busyStudent(int[] startTime, int[] endTime, int queryTime) {
        int max = Arrays.stream(endTime).max().getAsInt();
        if (max < queryTime) {
            return 0;
        }

        int[] queryArr = new int[max + 2];

        // 差分数组的操作，再区间[i,j]内加一个数x，就是将arr[i]+x，arr[j+1]-x
        for (int i = 0; i < startTime.length; i++) {
            // 此时映射再区间中
            queryArr[startTime[i]]++;
            queryArr[endTime[i] + 1]--;
        }

        int ans = 0;
        // 搜索queryTime区间中有没有作业
        // 对差分数组求前缀和，可以得到统计出 tt 时刻正在做作业的人数。
        for (int i = 0; i <= queryTime; i++) {
            ans += queryArr[i];
        }

        return ans;
    }*/

        // 二分查找
        // 找到起始时间小于queryTime的学生集合A
        // 找到结束时间小于queryTime的学生集合B，还有一部分肯定大于queryTime
        // 此时B是A的子集，所以
        // A的个数减去B的个数就可以得到满足的学生
        // https://leetcode.cn/problems/number-of-students-doing-homework-at-a-given-time/solution/zai-ji-ding-shi-jian-zuo-zuo-ye-de-xue-s-uv49/
        public int busyStudent(int[] startTime, int[] endTime, int queryTime) {
            Arrays.sort(startTime);
            Arrays.sort(endTime);
            int lowerbound = lowerbound(endTime, 0, endTime.length - 1, queryTime);
            int upperbound = upperbound(startTime, 0, startTime.length - 1, queryTime);
            return upperbound - lowerbound;
        }

        public int upperbound(int[] arr, int l, int r, int target) {
            // 返回的是个数
            int ans = r + 1;
            while (l <= r) {
                int m = l + (r - l) / 2;
                if (target < arr[m]) {
                    ans = m;
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }

            return ans;
        }

        public int lowerbound(int[] arr, int l, int r, int target) {
            // 返回的是个数
            int ans = r + 1;
            while (l <= r) {
                int m = l + (r - l) / 2;
                if (target <= arr[m]) {
                    ans = m;
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }

            return ans;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
